package src.leetcode.backtrack.medium_0216;

import java.util.ArrayList;
import java.util.List;

public class combinationSum3 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum3(3, 7));
    }
}

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 1; i < 10; i++){
            List<Integer> list = new ArrayList<>();
            list.add(i);
            int sum = i;
            combinationHelper(i + 1, k - 1, n, sum, list, ans);
        }
        return ans;
    }

    public void combinationHelper(int i, int k, int n, int sum, List<Integer> list, List<List<Integer>> ans){
        if (sum == n && k == 0) {
            ans.add(list);
            return;
        }
        if (sum != n && k == 0) {
            return;
        }
        for (; i < 10; i++){
            List<Integer> newlist = new ArrayList<>(list);
            System.out.println(newlist);
            newlist.add(i);
            combinationHelper(i + 1, k - 1, n, sum + i, newlist, ans);
        }
    }
}
